THE QUICKEST SORT? by Ron Andrews Is the sort routine I am about to describe really the quickest? Perhaps not; however, I have yet to find one that will beat it in sorting arrays of random numbers. Some time ago (years, in fact), I had need of a sort function to use in a PLI-80 program. I eventually found a really good non- recursive version of the quicksort algorithm in Niklaus Wirth's book "Algorithms + Data Structures = Programs". I translated the routine (which was written in Pascal) into PLI-80, and found it to be quite fast. Some time later, I needed a sort function for the Whitesmiths RT-11 "C" compiler because of a serious bug in the supplied function (when given a sorted array, it recursed itself to death). When testing the new function (written in "C"), I found it to be significantly faster than the supplied routine. The speed gain is probably due to the non-recursive nature of the algorithm. Since then, I have modified it for all the "C" compilers which I use. The major modification that I have made to the routine is the ability to sort almost anything, not just arrays. The sort function has no knowledge of the data being sorted except for the number of items. As an example, the Unix-style "qsort" function supplied with most "C" compilers will not sort multiple items such as a separate "x", "y", and "z" arrays to sort "z" within "y" within "x". Defining a structure "struct xyz { int x,y,z; } xyz[n];" will do something similar and can be sorted; however, this is not always practical. The data "int x[n],y[n],z[n];" (which might have come 1 from a FORTRAN program) cannot be sorted with the standard "qsort" function. The algorithm is quite flexible and may even be (and actually was) re-written in FORTRAN or assembler. Versions have been adapted to sort arrays of integers, floats, and doubles. The original algorithm in the book actually sorted arrays. The function is called as follows: "rqsort(n,load,check,swap);" "n" is the number of items to sort (2 - 32767 only). "load(i)" is a function which loads item "i" into temporary storage. The temporary storage must be static and external to the "load" and "check" functions since it is used by both. "check(i)" is a function which compares the stored item with item "i". Return -1 if temporary < item "i". Return 0 if temporary == item "i". Return 1 if temporary > item "i". It is mandatory that all three conditions be checked! "swap(i,j)" is a function which swaps items "i" and "j". Obviously the functions need intimate knowledge of the items being sorted. Unfortunately, there is a restriction on the number of objects that can be sorted when using 16-bit integers. Since most objects are integers or larger and a segment on an 8088-based computer is only 32768 integers in length, this in not too much of a restriction. This restriction does not apply to systems using 32- bit integers; however, the size of "stackl" and "stackr" in the function should be increased to 36 in order to accommodate more items. Note that the "unsigned" cast is used in calling the "load" 2 function to prevent integer overflow from causing a negative value when using 16-bit integers. It should not be necessary when using 32-bit integers. Of course, the function must be compiled for the correct model. I have used the "static" declaration with the local variables since this causes slightly faster execution times on an 8088 processor. It should make no difference with an 80286 or 80386 processor. The general purpose, double, float, and integer versions of the sort function are included in this package. Sample "load", "check", and "swap" functions to sort "z" within "y" within "x" are also included. I have compared the "C" versions of the algorithm using several compilers on a PC clone running PC-DOS 3.1 at 8 MHz and on two Unix systems. The sort functions were compiled with the compiler being tested. It should be mentioned that the Computer Innovations "C" compiler was a very old one made in 1984; however, this was not a compiler test. The test was to compare the supplied "qsort" function with the new functions. All three PC-DOS compilers have more recent versions available. With the Unix systems, I was the only user at the time. The integer size on these systems was 32 bits. The differences in timing are shown in the accompanying table. This may not be the quickest sort around. In some cases, such as already sorted objects, it is not. Despite some shortcomings, I think it can be a valuable tool where the maximum speed and versatility is required. 3 ----------------end-of-author's-documentation--------------- Software Library Information: This disk copy provided as a service of The Public (Software) Library We are not the authors of this program, nor are we associated with the author in any way other than as a distributor of the program in accordance with the author's terms of distribution. Please direct shareware payments and specific questions about this program to the author of the program, whose name appears elsewhere in this documentation. If you have trouble getting in touch with the author, we will do whatever we can to help you with your questions. All programs have been tested and do run. To report problems, please use the form that is in the file PROBLEM.DOC on many of our disks or in other written for- mat with screen printouts, if possible. The P(s)L cannot de- bug programs over the telephone. Disks in the P(s)L are updated monthly, so if you did not get this disk directly from the P(s)L, you should be aware that the files in this set may no longer be the current versions. For a copy of the latest monthly software library newsletter and a list of the 1,400+ disks in the library, call or write The Public (Software) Library P.O.Box 35705 - F Houston, TX 77235-5705 (713) 665-7017